package org.glutenberg.util.binarytree;

import java.util.Enumeration;

public class SymmetricTraversal implements Enumeration {

	private TreeItem current;
	
	public SymmetricTraversal(Tree t){
		this.goToFirst(t.getRoot());
	}
	
	private void goToFirst(TreeItem subTree){
		current = subTree;
		while(current!=null && current.getLeftChild()!=null) current = current.getLeftChild();		
	}
	
	private void goToNextAncestor(){
		TreeItem next = current.getParent();
		if(current.isRightChild()){
			while(next!=null && !next.isLeftChild()){
				next = next.getParent();
			}
			if(next!=null){
				next = next.getParent();
			}			
		}
		current = next;
	}
	
	public boolean hasMoreElements() {
		return current!=null;
	}

	public Object nextElement() {
		TreeItem ret = current;
		if(current.getRightChild()!=null){
			this.goToFirst(current.getRightChild());
		} else if(current.getParent()!=null){
			this.goToNextAncestor();
		} else current = null;
		if(ret!=null) return ret.getKey();
		return ret;
	}

}
